package Algorithm.dynamicProgramming.introduct;

/**
 * 70. 爬楼梯 https://leetcode.cn/problems/climbing-stairs
 * 题目简述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class ClimbStairs {

    /**
     * 动态规划
     * 1. 定义dp[i]: 爬到第i级台阶的方案数
     * 2. 确定递推公式：第i级台阶只可能由第i-1级台阶或者i-2级台阶爬上来，故dp[i] = dp[i-1] + dp[i-2]
     * 3. 初始化dp：dp[1] = 1;dp[2] = 2
     * 4. 开始遍历 递推到dp[n]
     */
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int p1=1, p2=2, r=3;
        for (int i=3;i <= n;i++) {
            r = p1 + p2;
            p1 = p2;
            p2 = r;
        }
        return r;
    }
}
